home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 476-500 / disk_500 / wiconify / wiconsetter.lzh / wIconSetter / Source / ListTree.c next >
C/C++ Source or Header  |  1991-04-19  |  7KB  |  185 lines
  1. /*
  2.  *  LISTREE.C             version 1.0
  3.  *
  4.  *  Converts sorted linked lists to balanced binary trees, and binary trees to
  5.  *  sorted linked lists.  These routines are non-recursive, so we don't have to
  6.  *  worry about stack size for large lists/trees.
  7.  *
  8.  *  Written for the Commodore Amiga 1000, version 1.3
  9.  *  using Lattice C v4.0 by Davide P. Cervone
  10.  */
  11.  
  12. #define NULL    0L
  13.  
  14. /*
  15.  *  ListItem is what must be at the head of each item in the list.
  16.  *  It also doubles as the left and right pointers of the binary tree.
  17.  */
  18.  
  19. struct ListItem
  20. {
  21.    struct ListItem *li_Next;
  22.    struct ListItem *li_Prev;
  23. };
  24. #define li_Left     li_Next
  25. #define li_Right    li_Prev
  26. #define li_BackUp   li_Left
  27.  
  28. #define SKIP_MISSING_NODE   (1<<1)
  29. #define NO_MISSING_NODE     (1<<0)
  30.  
  31.  
  32. /*
  33.  *  *ListToTree()
  34.  *
  35.  *  Count the items in the list, if they weren't already counted for us.
  36.  *  Find the smallest power of two greater than the count.  If there were
  37.  *  exactly this many (minus one) items in the list, it would make a perfect
  38.  *  balanced binary tree.  If there are not this many, we will use this basic
  39.  *  form, but leave some of the lowest level empty.  We proceed by assuming
  40.  *  that it has the full number, and skip items when necessary.
  41.  *    As we build the tree, all the nodes to the left of the current node will
  42.  *  be correct, nodes on the right may be modified as we go, however, and
  43.  *  we will use the li_Right pointer to maintain back pointers to previous
  44.  *  higher-up nodes in the tree (this takes the place of the recusion stack).
  45.  *  At any given point, anything interior to the current tree is correctly 
  46.  *  linked, but the nodes along the right-hand (of every level) have their
  47.  *  li_Right pointers pointing upeward to the level above (towards the root).
  48.  *    In a perfect binary tree, the binary representation of item's position
  49.  *  in the list is used to determine its position in the tree:  the position
  50.  *  of the least-significant 1 bit in the number tells which level of the tree
  51.  *  that item should be in.  For example, if the number is 100 (binary), then
  52.  *  the item is at the third level from the bottom of the tree.  The trick will
  53.  *  be to assign numbers to the items in a list that is not of a perfect length.
  54.  *
  55.  *  The main loop counts off the numbers in the perfect-sized list.
  56.  *    The next loop finds the node's level within the tree by looking along
  57.  *      the back pointers (held in li_Right) until we reach the correct level.
  58.  *      PreviousNode will point to the node to the left of the current item,
  59.  *      and CurrentNode will become the back pointer for the current item.
  60.  *    The only nodes that will be missing from a perfect balanced tree will
  61.  *      be in the bottom level, so if the current item is to be in the bottom
  62.  *      level (mask == 1) we check for whether we need to skip this position
  63.  *      in the tree:  we could simply check whether num > Count, but this
  64.  *      would leave all the missing items at one end of the level; we would
  65.  *      prefer them to be more evenly intermixed, so we reverse the bits in
  66.  *      num and then do the check.
  67.  *    If the number is not to be skipped, and there is an item to add,
  68.  *      We link the previous node into the left of the current node
  69.  *      and make li_Right point back to the next level up.
  70.  *      Indicate that no nodes are to be skipped.
  71.  *    Otherwise indicate that a node (in the perfect tree) is to be skipped.
  72.  *  The loop is repeated until every node is placed in the tree.  The very last
  73.  *  pass in the loop causes the right-hand nodes to become properly linked, 
  74.  *  and leaves the pointer to the top-most node in the PreviousNode pointer.
  75.  *  This is returned as the root of the tree.
  76.  */
  77.  
  78. struct ListItem *ListToTree(CurrentItem,Count)
  79. struct ListItem *CurrentItem;
  80. int Count;
  81. {
  82.    struct ListItem *NextItem;
  83.    struct ListItem *CurrentNode = NULL;
  84.    struct ListItem *NextNode, *PreviousNode;
  85.    int num,temp,mask;
  86.    int MaxCount;
  87.    int MaskStart = NO_MISSING_NODE;
  88.    
  89.    if (Count == 0)
  90.       for (NextItem=CurrentItem; NextItem; NextItem=NextItem->li_Next,Count++);
  91.  
  92.    for (MaxCount=1; MaxCount<=Count; MaxCount<<=1);
  93.    
  94.    for (num = 1; num <= MaxCount; num++)
  95.    {
  96.       PreviousNode = NULL;
  97.       for (mask = MaskStart; (num & mask) == 0; mask <<= 1)
  98.       {
  99.          NextNode = CurrentNode->li_Right;
  100.          CurrentNode->li_Right = PreviousNode;
  101.          PreviousNode = CurrentNode;
  102.          CurrentNode = NextNode;
  103.       }
  104.       if (mask == 1)
  105.          for (temp=MaxCount | num; (temp>>=1)>1; mask = (mask<<1) | (temp & 1));
  106.         else
  107.          mask = 0;
  108.       if (mask <= Count)
  109.       {
  110.          if (CurrentItem)
  111.          {
  112.             NextItem = CurrentItem->li_Next;
  113.             CurrentItem->li_Left = PreviousNode;
  114.             CurrentItem->li_Right = CurrentNode;
  115.             CurrentNode = CurrentItem;
  116.             CurrentItem = NextItem;
  117.          }
  118.          MaskStart = NO_MISSING_NODE;
  119.       } else {
  120.          MaskStart = SKIP_MISSING_NODE;
  121.       }
  122.    }
  123.    return(PreviousNode);
  124. }
  125.  
  126.  
  127. /*
  128.  *  *TreeToList()
  129.  *
  130.  *  Start at the root of the tree, and an empty list
  131.  *  While there are more items in the tree
  132.  *    While there are nodes to the left
  133.  *      Save a pointer to where we last were in the tree
  134.  *      Move to the left in the tree
  135.  *    At this point, we have moved as far down the left side of the tree
  136.  *      as possible, at the same time saving our return path
  137.  *    Now repeat the following:
  138.  *      Link the node into the linked list and make it the new list-head
  139.  *      The next item will be the one to its right, if any
  140.  *      If there is no item to the right
  141.  *        Back up to the previous item (and recover the pointer to the node
  142.  *          before that)
  143.  *    Repeat this as long as there are no nodes on the right, and as long
  144.  *      as there is still a current node to work with.
  145.  *    At this point, we have moved back up the left-hand side of the tree,
  146.  *      adding nodes to the list until we come to one with a right-hand
  147.  *      branch.  The current node is not the first one on the right, and
  148.  *      we are ready to go down its left-hand side.  This continues until
  149.  *      all nodes are added to the list.  Note that as we proceed, the
  150.  *      PrevItem pointer may point farther and farther away in the tree.
  151.  *  Return the completed list.
  152.  */
  153.  
  154. struct ListItem *TreeToList(theRoot)
  155. struct ListItem *theRoot;
  156. {
  157.    struct ListItem *CurItem  = theRoot;
  158.    struct ListItem *PrevItem = NULL;
  159.    struct ListItem *list     = NULL;
  160.    struct ListItem *NextItem = NULL;
  161.  
  162.    while (CurItem != NULL)
  163.    {
  164.       while ((NextItem = CurItem->li_Left) != NULL)
  165.       {
  166.          CurItem->li_BackUp = PrevItem;
  167.          PrevItem = CurItem;
  168.          CurItem = NextItem;
  169.       }
  170.       do
  171.       {
  172.          if (list) list->li_Right = CurItem;
  173.          CurItem->li_Left = list;
  174.          list = CurItem;
  175.          NextItem = CurItem = CurItem->li_Right;
  176.          if (CurItem == NULL)
  177.          {
  178.             CurItem = PrevItem;
  179.             if (PrevItem) PrevItem = PrevItem->li_BackUp;
  180.          }
  181.       } while (NextItem == NULL && CurItem != NULL);
  182.    }
  183.    return(list);
  184. }
  185.